#pragma once
#include <iostream>
#include <assert.h>
using namespace std;

namespace My_BSTree 
{
	// 搜索二叉树 左边节点小于父节点，右边节点大于父节点
	template<class T>
	struct BSTreeNode
	{
		T _data;
		struct BSTreeNode<T>* _left;
		struct BSTreeNode<T>* _right;

		BSTreeNode(const T& data)
			:_data(data)
			, _left(nullptr)
			, _right(nullptr)
		{}
	};

	template<class T>
	class BSTree
	{
		typedef struct BSTreeNode<T> Node;
	public:
		bool Insert(const T& x)
		{
			if (_root == nullptr)
			{
				_root = new Node(x);
				return true;
			}
			Node* parent = nullptr;
			Node* cur = _root;
			while (cur)
			{
				if (cur->_data < x)
				{
					parent = cur;
					cur = cur->_right;
				}
				else if (cur->_data > x)
				{
					parent = cur;
					cur = cur->_left;
				}
				else
				{
					// 走到else说明搜索二叉树里面有这个值，所以就不用插入
					return false;
				}
			}
			if (parent->_left == cur && parent->_data > x)
				parent->_left = new Node(x);
			else
				parent->_right = new Node(x);

		}

		bool Find(const T& x)
		{
			Node* cur = _root;
			while (cur)
			{
				if (cur->_data < x)
				{
					cur = cur->_right;
				}
				else if (cur->_data > x)
				{
					cur = cur->_left;
				}
				else
				{
					return true;
				}
			}

			return false;
		}

		bool erase(const T& x)
		{
			assert(_root != nullptr);
			// 当只有一个根节点是特殊处理
			if (_root->_left == nullptr && _root->_right == nullptr)
			{
				delete _root;
				_root = nullptr;
				return true;
			}
			// 删除有两种情况
			// 1、删除的节点只有一个或者没有子节点
			// 2、删除的节点有两个节点
			Node* parent = nullptr;
			Node* cur = _root;
			while (cur)
			{
				// 第一种情况
				if (cur->_data > x)
				{
					parent = cur;
					cur = cur->_left;
				}
				else if (cur->_data < x)
				{
					parent = cur;
					cur = cur->_right;
				}
				else
				{
					// 处理的特殊情况 根节点是需要消除的节点 并且只有一个子节点
					if (cur == _root && cur->_left == nullptr)
					{
						_root = _root->_right;
						delete cur;
						return true;
					}
					if (cur == _root && cur->_right == nullptr)
					{
						_root = _root->_left;
						delete cur;
						return true;
					}
					int flag = 0;
					if (parent->_right == cur && cur->_left == nullptr)
					{
						parent->_right = cur->_right;
						flag = 1;
					}
					if (parent->_left == cur && cur->_left == nullptr)
					{
						parent->_left = cur->_right;
						flag = 1;
					}
					if (parent->_right == cur && cur->_right == nullptr)
					{
						parent->_right = cur->_left;
						flag = 1;
					}
					if (parent->_left == cur && cur->_right == nullptr)
					{
						parent->_left = cur->_left;
						flag = 1;
					}
					if (flag == 1)
					{
						delete cur;
						return true;
					}
					break;
				}
			}
			// 如果是正常情况下退出循环，说明没有找到要删除的数据
			if (cur == nullptr)
				return false;
			// 第二种情况
			// 可以选择在左边找一个最大值，或者在右边找一个最小值来替代删除的元素
			// 这里实现的是从右边找最小的
			Node* pt = nullptr;
			Node* rt = cur->_right;
			if (rt->_left == nullptr)
			{
				// 说明这个rt的节点就是右边最小的节点
				swap(rt->_data, cur->_data);
				cur->_right = rt->_right;
				delete rt;
				return true;
			}
			// 走到这块说明rt不是右边最小的节点
			while (rt->_left)
			{
				pt = rt;
				rt = rt->_left;
			}
			swap(rt->_data, cur->_data);
			delete rt;
			pt->_left = nullptr;
			return true;

		}

		void _InOrder(Node* root)
		{
			if (root == nullptr)
				return;
			_InOrder(root->_left);
			cout << root->_data << " ";
			_InOrder(root->_right);
		}

		// 查找二叉树的中序遍历刚好是顺序排序
		void InOrder()
		{
			// 中序遍历需要递归来解决，所以这个 _root 不好传 如果直接用_root 的话 _root 就会被改变
			Node* cur = _root;
			_InOrder(cur);
			cout << endl;
		}



	private:
		Node* _root = nullptr;
	};
}


namespace BSTree_Value
{
	// 搜索二叉树 左边节点小于父节点，右边节点大于父节点
	template<class T1 , class T2>
	struct BSTreeNode
	{
		T1 _data;
		T2 _value;
		struct BSTreeNode<T1,T2>* _left;
		struct BSTreeNode<T1,T2>* _right;

		// 默认构造
		BSTreeNode(const T1& data,const T2& value)
			:_data(data)
			,_value(value)
			,_left(nullptr)
			,_right(nullptr)
		{}

	};

	template<class T1,class T2>
	class BSTree
	{
		typedef struct BSTreeNode<T1,T2> Node;
	public:
		BSTree() = default;

		// 拷贝构造 (深拷贝)
		BSTree(const BSTree& x)
		{
			_root = _BSTreeConstruct(x._root);
		}

		bool Insert(const T1& x,const T2& value)
		{
			if (_root == nullptr)
			{
				_root = new Node(x,value);
				return true;
			}
			Node* parent = nullptr;
			Node* cur = _root;
			while (cur)
			{
				if (cur->_data < x)
				{
					parent = cur;
					cur = cur->_right;
				}
				else if (cur->_data > x)
				{
					parent = cur;
					cur = cur->_left;
				}
				else
				{
					// 走到else说明搜索二叉树里面有这个值，所以就不用插入
					return false;
				}
			}
			if (parent->_left == cur && parent->_data > x)
				parent->_left = new Node(x,value);
			else
				parent->_right = new Node(x,value);

		}

		Node* Find(const T1& x)
		{
			Node* cur = _root;
			while (cur)
			{
				if (cur->_data < x)
				{
					cur = cur->_right;
				}
				else if (cur->_data > x)
				{
					cur = cur->_left;
				}
				else
				{
					return cur;
				}
			}

			return nullptr;
		}

		bool erase(const T1& x)
		{
			assert(_root == nullptr);
			// 当只有一个根节点是特殊处理
			if (_root->_left == nullptr && _root->_right == nullptr)
			{
				delete _root;
				_root = nullptr;
				return true;
			}
			// 删除有两种情况
			// 1、删除的节点只有一个或者没有子节点
			// 2、删除的节点有两个节点
			Node* parent = nullptr;
			Node* cur = _root;
			while (cur)
			{
				// 第一种情况
				if (cur->_data > x)
				{
					parent = cur;
					cur = cur->_left;
				}
				else if (cur->_data < x)
				{
					parent = cur;
					cur = cur->_right;
				}
				else
				{
					// 处理的特殊情况 根节点是需要消除的节点 并且只有一个子节点
					if (cur == _root && cur->_left == nullptr)
					{
						_root = _root->_right;
						delete cur;
						return true;
					}
					if (cur == _root && cur->_right == nullptr)
					{
						_root = _root->_left;
						delete cur;
						return true;
					}
					int flag = 0;
					if (parent->_right == cur && cur->_left == nullptr)
					{
						parent->_right = cur->_right;
						flag = 1;
					}
					if (parent->_left == cur && cur->_left == nullptr)
					{
						parent->_left = cur->_right;
						flag = 1;
					}
					if (parent->_right == cur && cur->_right == nullptr)
					{
						parent->_right = cur->_left;
						flag = 1;
					}
					if (parent->_left == cur && cur->_right == nullptr)
					{
						parent->_left = cur->_left;
						flag = 1;
					}
					if (flag == 1)
					{
						delete cur;
						return true;
					}
					break;
				}
			}
			// 如果是正常情况下退出循环，说明没有找到要删除的数据
			if (cur == nullptr)
				return false;
			// 第二种情况
			// 可以选择在左边找一个最大值，或者在右边找一个最小值来替代删除的元素
			// 这里实现的是从右边找最小的
			Node* pt = nullptr;
			Node* rt = cur->_right;
			if (rt->_left == nullptr)
			{
				// 说明这个rt的节点就是右边最小的节点
				swap(rt->_data, cur->_data);
				cur->_right = rt->_right;
				delete rt;
				return true;
			}
			// 走到这块说明rt不是右边最小的节点
			while (rt->_left)
			{
				pt = rt;
				rt = rt->_left;
			}
			swap(rt->_data, cur->_data);
			delete rt;
			pt->_left = nullptr;
			return true;

		}


		// 查找二叉树的中序遍历刚好是顺序排序
		void InOrder()
		{
			// 中序遍历需要递归来解决，所以这个 _root 不好传 如果直接用_root 的话 _root 就会被改变
			Node* cur = _root;
			_InOrder(cur);
			cout << endl;
		}

		~BSTree()
		{
			// 后序删除空间  左 右 根
			_BSTreeDestory(_root);
			_root = nullptr;
		}

	private:
		void _InOrder(Node* root)
		{
			if (root == nullptr)
				return;
			_InOrder(root->_left);
			cout << root->_data << ":" << root->_value << endl;
			_InOrder(root->_right);
		}

		void _BSTreeDestory(Node* root)
		{
			if (root == nullptr)
				return;
			_BSTreeDestory(root->_left);
			_BSTreeDestory(root->_right);
			delete root;
		}

		Node* _BSTreeConstruct(Node* root)
		{
			if (root == nullptr)
				return nullptr;
			// 这里深拷贝需要用到前序遍历   根 左 右
			Node* newnode = new Node(root->_data, root->_value);
			newnode->_left = _BSTreeConstruct(root->_left);
			newnode->_right = _BSTreeConstruct(root->_right);
			return newnode;
		}

		Node* _root = nullptr;
	};
}